# 有多少小于当前数字的数字: https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/


class Solution:
    def smallerNumbersThanCurrent(self, nums: list) -> list:
        """
            排序后计算
        """
        data = []
        # 将元素与它对应的原数组的下标进行绑定
        for i, num in enumerate(nums):
            data.append((i, num))
        
        # 以数值进行排序
        data.sort(key = lambda x: x[1])

        count = [0]*len(nums)
        # 开始遍历data计数
        prev = 0; 
        for i in range(len(data)):
            if i > 0 and data[i][1] != data[i-1][1]:
                prev = i
                count[data[i][0]] = prev
            else:
                count[data[i][0]] = prev
            """
            优化写法
            if i > 0 and data[i][1] != data[i-1][1]:
                prev = i
            count[data[i][0]] = prev
            """
        
        return count

nums = [8,1,2,2,3]

s = Solution()
s.smallerNumbersThanCurrent(nums)
